/**
 * Three distinct points are plotted at random on a Cartesian plane, such that
 * a triangle is formed. Consider the following two triangles:
 *
 *   A(-340,495), B(-153,-910), C(835,-947)
 *   X(-175,41),  Y(-421,-714), Z(574,-645)
 *
 * It can be verified that triangle ABC contains the origin, whereas triangle 
 * XYZ does not.
 *
 * Using triangles.txt, a text file containing the co-ordinates of one thousand 
 * triangles, find the number of triangles for which the interior contains the 
 * origin.
 */

#include <iostream>
#include <fstream>
#include "euler.h"

BEGIN_PROBLEM(102, solve_problem_102)
	PROBLEM_TITLE("Count triangles that contain the origin")
	PROBLEM_ANSWER("228")
	PROBLEM_DIFFICULTY(1)
	PROBLEM_FUN_LEVEL(2)
	PROBLEM_TIME_COMPLEXITY("n")
	PROBLEM_SPACE_COMPLEXITY("1")
	PROBLEM_KEYWORDS("geometry")
END_PROBLEM()

static bool triangle_contains_origin(int x1, int y1, int x2, int y2, int x3, int y3)
{
	auto det = [](int x1, int y1, int x2, int y2) -> int {
		return x1*y2 - x2*y1;
	};
	int d1 = det(x1,y1,x2,y2);
	int d2 = det(x2,y2,x3,y3);
	int d3 = det(x3,y3,x1,y1);
	return (d1 > 0 && d2 > 0 && d3 > 0) || (d1 < 0 && d2 < 0 && d3 < 0);
}

static void solve_problem_102()
{
	int count = 0;
	std::ifstream fs("input/triangles.txt");
	
	int x1, y1, x2, y2, x3, y3;
	char c;
	// -340,495,-153,-910,835,-947
	while (fs >> x1 >> c >> y1 >> c >> x2 >> c >> y2 >> c >> x3 >> c >> y3)
	{
		bool contains = triangle_contains_origin(x1,y1,x2,y2,x3,y3);
		if (contains)
			++count;
	}
	std::cout << count << std::endl;
}
